For our purposes, curves and surfaces will be referred to as shapes, and polygonal curves and polyhedral surfaces will be referred to as piece-wise linear shapes, respectively.
In many applications, particularly in visualization of scientific data, and as intermediate steps within a number of other procedures, polygonal curve approximations of two and three dimensional curves, and polyhedral surface approximations of surfaces, are routinely determined. An inherent problem of these piece-wise linear approximation methods is that the resulting piece-wise linear shapes appear faceted. To reduce the apparent faceting, smoothing methods are used.
Smoothing methods are also used in the Computer Graphics and Geometric Modeling literature within the context of curve and surface design. Subdivision surfaces are designed as limits of sequences of polyhedral surfaces. Starting with an initial skeleton polyhedral surface, the next polyhedral surface in the sequence is obtained by subdividing all the faces of the current surface, and then applying a polyhedral surface smoothing step to the subdivided surface. The main problem with most of these surface design methods is that the limiting surface is significantly smaller in size than the initial skeleton surface. Subdivision curves are defined likewise and suffer the same problems.
Boundary-following and iso-surface construction algorithms are prior art examples of algorithms that produce these piece-wise linear approximations. In general, algorithms to compute piece-wise linear approximations of smooth curves and surfaces differ depending on how the original curve or surface is described. Among the most common descriptions, curves and surfaces can be described analytically by parametric or implicit equations.
The prior art recognizes that implicit curves and surfaces (i.e., those defined by implicit equations) are particularly difficult to approximate. Points of implicit curves and surfaces are determined by solving systems of equations. Alternatively, points of parametric curves are more easily obtained by substituting values for one parametric variable (parametric surfaces are defined by two variables) in a set of parametric equations.
Implicit and parametric curves and surfaces are defined by functions. Functions can be expressed as analytic formulas or as tables of values. When the functions are defined by tables of values, it may be necessary to determine intermediate values by interpolation. Boundary or contour following algorithms produce typical examples of two-dimensional parametric curves or surfaces that are defined by tables of values. These are curves extracted from digital images as the boundary curves of image regions. The table of values is constructed as the sequence of coordinates of the boundary vertices of the pixels visited while following the boundary of the region, which constitute a polygonal approximation of an underlying smooth curve. The state of the art in contour following algorithms was disclosed in the prior art by the year 1973.
An iso-surface construction algorithm computes a piece-wise linear approximation of an implicit surface from the table of values that the defining function attain on a regular three dimensional grid. The so-called marching cubes algorithm is one of the most widely known iso-surface construction algorithms, but there exists in the prior art a large family of closely related algorithms, which differ essentially in how they tessellate the volume defined by the grid of function values, and on how they interpolate function values between existing table values.
The main problem with almost all of these approximation algorithms is that, even though the underlying curve or surface is smooth, the resulting piece-wise linear shape appears faceted. This is so because, due to the discretization or interpolation processes, the location of points on the underlying curve or surface cannot be determined with high precision. FIG. 1 is a prior art example of piece-wise linear approximations of smooth curves and surfaces showing the faceting problem. A smooth curve approximation algorithm produces a faceted piece-wise linear approximation 120 of a smooth curve 110. A smooth surface approximation algorithm produces a faceted piece-wise linear approximation 140 of a smooth curve 130.
The prior art provides essentially two approaches to solve the smoothing problem regarding surfaces--visual smoothing and geometric smoothing. Visual smoothing uses variations of illumination to make piece-wise linear surfaces appear smooth without changing the surface. (This technique does not exist for curves.) Geometric smoothing modifies the geometry of the curve or surface to perform actual smoothing.
In visual smoothing, different illumination models and face shading algorithms can be used to produce a visually smoothing effect. Among these algorithms there are those that define the surface normal at a vertex of the polyhedral surface as a weighted average of the surface normals of the incident faces, and use these computed surface normals at the vertices to produce a smooth shading of the surface using the so-called Phong shading method, also known as normal-vector interpolation shading. Using these methods, the surface geometry is not modified, but just rendered in such a way that it looks smooth.
Visual smoothing methods are of no use when the surface approximation is determined with some other purpose in mind, such as for example, to locate points of high curvature or other geometric invariant features on the curve or surface for identification or registration applications, to measure curve length, surface area, area enclosed by a closed curve, or volume enclosed by a closed surface. In these cases the geometry of the polyhedral surface must be modified to achieve accurate results in the computations performed afterwards.
Most prior art geometric smoothing methods suffer from a number of problems. Perhaps the most important one is the shrinkage problem: when applied iteratively a large number of times, a shape eventually converges to its centroid. FIG. 2A illustrates the problem of shrinkage that most prior art smoothing algorithms have in the case of curves, and FIGS. 2B illustrates the same problem in the case of surfaces. FIG. 2 is a prior art example of the shrinkage problem. A shrinking piece-wise linear curve smoothing algorithm produces a smoother but smaller piece-linear curve 220 when applied to a piece-linear curve 210. A shrinking piece-wise linear surface smoothing algorithm produces a smoother but smaller piece-linear surface 240 when applied to a piece-linear surface 230.
In geometric smoothing, smoothing polygonal curves is simpler than smoothing polyhedral surfaces because curves have an intrinsic linear ordering. For a closed curve, the fact that each vertex has exactly two neighbors in the intrinsic ordering, one preceding it and the other following it, allows for the application of Fourier analysis. The so-called Fourier descriptors--the use of the coefficients in a Fourier series expansion of the tangent-angle versus arc-length description of a curve--provide a multi-resolution representation of continuous curves. To smooth a curve it is sufficient to truncate its Fourier series. However, the result is no longer a polygonal curve, but a smooth parametric curve defined by analytic equations. To obtain a new polygonal curve, the new continuous curve, the truncated Fourier series of the original curve, is sampled at regular intervals. Fourier descriptors date back to the early 1960's, and have been widely used since then in the computer vision literature as multi-resolution shape descriptors for object recognition. In practice, this continuous process is approximated by computing the Discrete Fourier Transform of the sequence of vertex coordinates, setting the coefficients of the transform associated with high frequencies to zero, and back transforming the resulting sequence.
The method of Fourier descriptions for curve smoothing does not have the shrinkage problem, but it is well known in the prior art that truncating the Fourier series of a function introduces an unwanted high frequency perturbation. This problem is known in the prior art as the Gibbs phenomenon. There are two other important problems with this method for smoothing polyhedral curves. First, it is rather computationally expensive. Even using the Fast Fourier Transform algorithm, the number of arithmetic operations is of the order of n log(n), where n is the number of vertices. Linear algorithms, those which require in the order of n arithmetic operations, are more desirable, particularly for surfaces, where the number of vertices is large. The second problem with the method of fourier descriptions is that it does not extend to surfaces of arbitrary topological type, but just to surfaces that can be parameterized with vector functions of two variables defined on a rectangular region. And even in these cases, the results are dependent on the particular parameterization used. In the case of curves the intrinsic order determines a canonical parameterization, the arc-length parameterization, but there is no such a thing in the case of surfaces.
Perhaps the most popular linear (the number of operations are proportional to the number faces, edges, or vertices of the piece-wise linear shape) technique of geometric smoothing parameterized curves is the so-called Gaussian filtering method. In the continuous case, Gaussian filtering is performed by convolving the vector function that parameterizes the curve with a Gaussian kernel. Gaussian filtering also extends to those surfaces that can be parameterized by functions of two variables defined on a rectangular domain, but not to surfaces of arbitrary topological type because there is not even a valid notion of convolution for general surfaces. Gaussian filtering is applied to images in this way, because images are modeled as graphs of functions of two variables. But it is well known though that Gaussian filtering has the difficulty that it produces shrinkage. Some heuristic solutions to this problem have been proposed, and more recently Oliensis presented a better analysis of the problem and an elegant solution. By looking at the filtered curve in the frequency domain, and because the Fourier transform of a convolution is the product of the Fourier transforms of the two factors, Oliensis showed that the shrinkage problem is a consequence on the fact that the Fourier transform of a Gaussian kernel, a Gaussian function itself, does not constitute a low-pass filter. Except for the zero frequency, all the frequencies are attenuated. Since an ideal low-pass filter has infinite support in the space domain, the problem is difficult to solve, but Oliensis proceeded to define a low-pass filter kernel that solves the problem. That is, convolution of a curve with this kernel produces smoothing without shrinkage. The main problem with this method is that it does not extend to surfaces of arbitrary topological type either, i.e., it only applies to surfaces where the neighborhood is defined by a rectangular grid. This is so mainly because of two reasons. First, although almost compact, the significant part of the support of the kernel must extend significantly far away from the current vertex to produce a significant smoothing effect. And second, based on the usual representation of a polyhedral surface as a list of vertices and a list of faces, it is very difficult to access vertices that are far away from a given vertex without building special purpose data structures. Furthermore, for a general surface the neighborhood structure changes from vertex to vertex, and so, a different kernel should be designed for each vertex, consuming a significant amount of storage. All of this is very impractical, both in terms of the number of arithmetic operations and in terms of the amount of storage required to encode all this information.
In the Computer Graphics and Geometric Modeling literature, surface smoothing is also called surface fairing, and is usually associated with patch technology. In this framework surface fairing is case as a smooth surface interpolation problem where each planar face of the initial polyhedral surface is replaced by a smooth parametric patch. Since algorithms in this group produce interpolating surfaces, they do not suffer from the shrinkage problem, but a significant amount of high curvature variation from the skeleton polyhedron might remain present in the resulting surfaces. That is, the problem of smoothing the skeleton polyhedral surface is not solved. In that sense, these methods are somehow like the visual smoothing methods described above. Furthermore, the resulting surfaces are no longer polyhedral, and so, cannot be compared with other geometric smoothing algorithms. More recently surface fairing has been formulated as a global nonlinear minimization problem on a polyhedral surface, with a number of degrees of freedom proportional to the number of vertices or faces of the surface. Some of these algorithms produce interpolating surfaces as well, but at the expense of a very high computational cost, and others do produce shrinkage.
The weighted averaging method is the simplest approximation of Gaussian smoothing for polygonal curves and polyhedral surfaces. In the weighted averaging method the new position of each vertex is computed as a weighted average of the current position of the vertex, and the current position of its first order neighbors, those vertices that share an edge (or face) with the current vertex. The weighted averaging method has a number of advantages with respect to the prior art discussed above, but still produces shrinkage. The first advantage is that it applies to polygonal curves and polyhedral surfaces of arbitrary topological type, not only those that can be parameterized by functions defined on a rectangular domain. The second advantage is that, since first order neighbors are defined implicitly in the list of edges or faces of the curve or surface, no storage is required to encode the neighborhood structures. The third advantage is that the number of operations is a linear function of the total number of vertices and faces.